package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 10. 正则表达式匹配
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/25 13:52
 */
public class IsMatch {

    public static void main(String[] args) {
        IsMatch test = new IsMatch();

        String[] ss = {"aa", "aa", "ab", "aab", "abc",
                "mississippi", "aaa", "aaaaaa", "aaa", "bbbba",
                "bbbb"};
        String[] ps = {"a", ".*", ".*", "c*a*b", "ab*",
                "mis*is*p*.", ".a", ".*", "a*", ".*a*a",
                ".c*."};

        boolean[] values = {false, true, true, true, false,
                false, false, true, true, true,
                false};
        for (int i = 0; i < ss.length; i++) {
            boolean match = test.isMatch(ss[i], ps[i]);
            if (match != values[i]) {
                System.out.println(i + "  " + ss[i] + "  " + ps[i] + "   " + values[i]);
            }
        }
        System.out.println("ok");
    }

    public boolean isMatch(String s, String p) {
        int a = s.length();
        int b = p.length();
        boolean[][] arr = new boolean[a + 1][b + 1];
        char[] ac = s.toCharArray();
        char[] bc = p.toCharArray();
        arr[0][0] = true;
        for (int i = 1; i <= b; i++) {
            if (bc[i - 1] == '*') {
                arr[0][i] = arr[0][i - 2];
            }
        }
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (ac[i] == bc[j] || bc[j] == '.') {
                    arr[i + 1][j + 1] = arr[i][j];
                    continue;
                }
                arr[i + 1][j + 1] = bc[j] == '*'
                        && ((arr[i + 1][j] || arr[i + 1][j - 1]) || ((arr[i][j] || arr[i][j + 1])
                        && (bc[j - 1] == ac[i] || bc[j - 1] == '.')));
            }
        }
        return arr[a][b];
    }

}
